class NumMatrix {
    vector<vector<int>> dp;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int a=matrix.size()+1;int b=matrix[0].size()+1;
        dp.resize(a,vector<int>(b));
        for(int i=1;i<=a-1;i++)
        for(int j=1;j<=b-1;j++)
        dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1];
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int x1=row1+1;
        int y1=col1+1;
        int x2=row2+1;
        int y2=col2+1;
        return dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1];
    }
};


